package com.example.algorithm.linked_list;

import java.util.LinkedList;

//反转单向链表
//要求：ReverseList方法的参数是原链表头节点，返回结果要求是反转后的链表头节点

// 下面这个例子我自己写的有毛病。LinkedList是双向链表，它可不是单向链表呢。
// Java中没有内置的单向链表类。但是，您可以通过创建自定义类来实现单向链表。通常，单向链表由节点组成，每个节点包含数据和指向下一个节点的引用。您可以创建一个表示节点的类，并在其中实现插入、删除、搜索等方法，以构建单向链表的功能。
// 如果要创建一个单向列表的结构，需要自己手动实现。请看 ReverseLinkedListSolution02
public class ReverseLinkedListSolution {

    public static void main(String[] args) {
        LinkedList ll = new LinkedList<ListNode>();
        ll.add(new ListNode(-1));
        ll.add(new ListNode(3));
        ll.add(new ListNode(6));
        ll.add(new ListNode(12));
        ll.add(new ListNode(20));

        System.out.println("反转前：");
        System.out.println(ll);

        System.out.println("反转后：");
        //for (ListNode ln : ll) {
        //
        //}
    }

    public ListNode ReverseList(ListNode head) { //入参是头部节点

        //处理空链表 fast-template
        if (head == null)
            return null;


        //pre和cur变量做初始化
        ListNode pre = null; // 当前节点的前一个节点。它是指反转之后
        ListNode cur = head; // 当前循环循环到的节点


        //循环遍历
        while (cur != null) {

            // 凡是遇到temp这种临时取出来的变量，不用太多想它的逻辑作用。它无非就是这个数据后续要用到，但是我先取出来放着，免得存放数据的存放者被改了我后续再取，数据就不对了。
            // 取出当前节点的下一个，留待下次循环作为当前节点
            ListNode temp = cur.next;


            // 核心语句：修改指向关系
            //当前节点的前一个，赋值给当前节点作为下一个
            cur.next = pre;


            // 初始化下一轮的pre
            pre = cur;

            // 旧列表的下一个给下一轮。当当前。
            cur = temp;
        }
        return pre;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

